package week_plan;

import java.util.Stack;

/**
 * Created by xupeng20 on 2019/3/18.
 */
public class MyStack {
    /**
     * 实现一个特殊的栈，在实现栈的基本功能基础上，再返回栈中最小元素的操作。
     */
    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;
    public MyStack(){
        this.stackData = new Stack<Integer>();
        this.stackMin = new Stack<Integer>();
    }
    //第一种方法 开始
    public void push(int newNum){
        if (this.stackMin.isEmpty()){
            this.stackMin.push(newNum);
        }else if (newNum<=this.getMin()){
            //比stackMin里面的最小值小 压入stackMin
            this.stackMin.push(newNum);
        }
        //正常的压入操作
        this.stackData.push(newNum);
    }

    public int pop(){
        if (this.stackData.isEmpty()){
            throw new RuntimeException("你的stack是空的！");
        }
        //正常的弹出
        int value = this.stackData.pop();
        if (value == this.getMin()){
            //说明弹出的值是stackData中的最小值 ，对应着stackMin中也对应弹出
            this.stackMin.pop();
        }
        return value;
    }
    //第一种方法 结束

    //第二种方法 开始
    public void push2(int newNum){
        if (this.stackMin.isEmpty()){
            this.stackMin.push(newNum);
        }else if (newNum <= this.getMin()){
            this.stackMin.push(newNum);
        }else {
            // 对应的将 最小值放入到对应的位置
            int min = this.stackMin.peek();
            this.stackMin.push(min);
        }
        this.stackData.push(newNum);
    }

    public int pop2(){
        if (this.stackData.isEmpty()){
            throw new RuntimeException("你的stack是空的！");
        }
        //按顺序都弹出即可
        this.stackMin.pop();
        int value = this.stackData.pop();
        return value;
    }
    //第二种方法 结束

    //两种方法对比：所有的操作时间复杂度为O(1)、空间复杂度为O(n)
    //区别：第一种压入稍微省空间 但是弹出费时间，第二种压入费空间、弹出省时间




    public int getMin(){
        if (this.stackMin.isEmpty()){
            throw new RuntimeException("你的stack是空的！");
        }
        //peek  查看栈中元素而不移除他
        return this.stackMin.peek();
    }

}
